
public class MergeMain {

	public static void main(String[] args) {
		int[] numeros = {3,4,7,1,9,2};
		int[] retorno = mergeSort(numeros) ;
		for (int t=0; t < retorno.length; t++){
			System.out.print(retorno[t]+" ");
		}
	}

	private static int[] mergeSort (int[] inteiros) {
		int div = inteiros.length / 3;
		int ini = 0;
		int fim = inteiros.length - 1;
		if (fim < 2) {
			if (fim == 1){
				int aux[] = inteiros;
				if (inteiros[0] < inteiros[1]) return inteiros;
				else {
					int temp = inteiros[0];
					inteiros[0] = aux[1];
					inteiros[1] = temp;
					return inteiros;
				}
			} else return inteiros;
		} else {
			int[] inteiros1 = divideArray(inteiros, ini, div-1);
			inteiros1 = mergeSort(inteiros1);
			int[] inteiros2 = divideArray(inteiros, div, (fim-div));
			inteiros2 = mergeSort(inteiros2);
			int[] inteiros3 = divideArray(inteiros,(fim-div+1), fim);
			inteiros3 = mergeSort(inteiros3);
			return (merge(inteiros1, inteiros2, inteiros3));
		}
	}

	private static int[] divideArray(int[] inteiros, int ini, int fim) {
		int[] retorno = new int[(fim-ini)+1];
		int pos = 0;
		for (int i = ini; i <= fim; i++) {
			retorno[pos++] = inteiros[i];
		}
		return retorno;
	}

	private static int[] merge(int[] inteiros1, int[] inteiros2, int[] inteiros3) {
		int[] retorno = new int[inteiros1.length + inteiros2.length + inteiros3.length];

		int i = 0;
		int j = 0;
		int k = 0;
		int posSolucao = 0;

		while (i != inteiros1.length && j != inteiros2.length && k != inteiros3.length) {
			if (inteiros1[i] < inteiros2[j] && inteiros1[i] < inteiros3[k]) {
				retorno[posSolucao++] = inteiros1[i];
				i++;
			} else if (inteiros1[i] > inteiros2[j] && inteiros2[j] < inteiros3[k]){
				retorno[posSolucao++] = inteiros2[j];
				j++;
			} else {
				retorno[posSolucao++] = inteiros3[k];
				k++;
			}
		}

		int[] daVez1;
		int[] daVez2;
		int ini1;
		int ini2;
		if (i == inteiros1.length) {
			daVez1 = inteiros2;
			daVez2 = inteiros3;
			ini1 = j;
			ini2 = k;
			while (ini1 != daVez1.length && ini2 != daVez2.length){
				if (daVez1[ini1] < daVez2[ini2]) {
					retorno[posSolucao++] = daVez1[ini1];
					ini1++;
				} else {
					retorno[posSolucao++] = daVez2[ini2];
					ini2++;
				}
			}
			if (ini1 == daVez1.length) {
				for (int a = ini2; a < daVez2.length; a++) {
					retorno[posSolucao++] = daVez2[a];
				}
			} else {
				for (int a = ini1; a < daVez1.length; a++) {
					retorno[posSolucao++] = daVez1[a];
				}
			}
		} else if (j == inteiros2.length) {
			daVez1 = inteiros1;
			daVez2 = inteiros3;
			ini1 = i;
			ini2 = k;
			while (ini1 != daVez1.length && ini2 != daVez2.length){
				if (daVez1[ini1] < daVez2[ini2]) {
					retorno[posSolucao++] = daVez1[ini1];
					ini1++;
				} else {
					retorno[posSolucao++] = daVez2[ini2];
					ini2++;
				}
			}
			if (ini1 == daVez1.length) {
				for (int a = ini2; a < daVez2.length; a++) {
					retorno[posSolucao++] = daVez2[a];
				}
			} else {
				for (int a = ini1; a < daVez1.length; a++) {
					retorno[posSolucao++] = daVez1[a];
				}
			}
		} else {
			daVez1 = inteiros1;
			daVez2 = inteiros2;
			ini1 = i;
			ini2 = j;
			while (ini1 != daVez1.length && ini2 != daVez2.length){
				if (daVez1[ini1] < daVez2[ini2]) {
					retorno[posSolucao++] = daVez1[ini1];
					ini1++;
				} else {
					retorno[posSolucao++] = daVez2[ini2];
					ini2++;
				}
			}
			if (ini1 == daVez1.length) {
				for (int a = ini2; a < daVez2.length; a++) {
					retorno[posSolucao++] = daVez2[a];
				}
			} else {
				for (int a = ini1; a < daVez1.length; a++) {
					retorno[posSolucao++] = daVez1[a];
				}
			}
		}
		return retorno;
	}
}
